package com.lun.other.tree;

import com.lun.util.BinaryTree.TreeNode;

public class MorrisTraversal {

	public String inorderTraverse(TreeNode root) {
		StringBuilder sb = new StringBuilder();
		inorderMorrisTraversal(root, sb);
		return sb.substring(0, sb.length() - 1);
	}

	private void inorderMorrisTraversal(TreeNode root, StringBuilder sb) {
		TreeNode cur = root, prev = null;
		while (cur != null) {
			if (cur.left == null) {// 1.如果curr左子节点为空：

				print(cur.val, sb);// 输出当前节点
				cur = cur.right;// curr指向它的右子节点，为下次循环作准备
			} else {
				// 2. 如果curr左子节点不为空，在curr的左子树中，找到curr在中序遍历下的前驱节点。
				prev = cur.left;
				while (prev.right != null && prev.right != cur)
					prev = prev.right;

				// 2.a 如果前驱节点的右孩子为空，
				if (prev.right == null) {// （这里curr第一次遍历到，建立连接）
					prev.right = cur; // 将它的右子节点设置为curr。（让当前节点与中序遍历下的前驱节点形成链接，这里形成）
					cur = cur.left; // curr指向它的 左子节点，为下次循环作准备
				} else {
					// 2.b 如果前驱节点的右子节点 为curr，（这里curr第二次遍历到，断开连接，打印值）
					print(cur.val, sb);
					prev.right = null;// 将它的右孩子重新设为空（断开链接，恢复树的形状）。
					cur = cur.right; // curr指向它的 左子节点，为下次循环作准备
				}
			}
		}
	}

	public String preorderTraverse(TreeNode root) {
		StringBuilder sb = new StringBuilder();
		preorderMorrisTraversal(root, sb);
		return sb.substring(0, sb.length() - 1);
	}

	private void preorderMorrisTraversal(TreeNode root, StringBuilder sb) {
		TreeNode cur = root, prev = null;
		while (cur != null) {
			if (cur.left == null) {

				print(cur.val, sb);
				cur = cur.right;
			} else {

				prev = cur.left;
				while (prev.right != null && prev.right != cur)
					prev = prev.right;

				if (prev.right == null) {
					// the only difference with inorder-traversal
					print(cur.val, sb); 
					prev.right = cur;
					cur = cur.left;
				} else {
					prev.right = null;
					cur = cur.right;
				}
			}
		}
	}

	public String postorderTraverse(TreeNode root) {
		StringBuilder sb = new StringBuilder();
		postorderMorrisTraversal(root, sb);
		return sb.substring(0, sb.length() - 1);
	}

	private void postorderMorrisTraversal(TreeNode root, StringBuilder sb) {
		TreeNode dump = new TreeNode(0);
		dump.left = root;
		TreeNode cur = dump, prev = null;
		while (cur != null) {
			if (cur.left == null) {
				cur = cur.right;
			} else {
				prev = cur.left;
				while (prev.right != null && prev.right != cur)
					prev = prev.right;

				if (prev.right == null) {
					prev.right = cur;
					cur = cur.left;
				} else {
					printReverse(cur.left, prev, sb); // call print
					prev.right = null;
					cur = cur.right;
				}
			}
		}
	}

	// print the reversed tree nodes 'from' -> 'to'
	private void printReverse(TreeNode from, TreeNode to, StringBuilder sb) {
		reverse(from, to);

		TreeNode p = to;
		while (true) {
			print(p.val, sb);
			if (p == from)
				break;
			p = p.right;
		}

		reverse(to, from);
	}

	// reverse the tree nodes 'from' -> 'to'.
	private void reverse(TreeNode from, TreeNode to) {
		if (from == to)
			return;
		TreeNode x = from, y = from.right, z;
		while (true) {
			z = y.right;
			y.right = x;
			x = y;
			y = z;
			if (x == to)
				break;
		}
	}

	private void print(int val, StringBuilder sb) {
		sb.append(val);
		sb.append(',');
	}

}
